Dijkstra's algorithm can be expressed formally as follows:

G    - arbitrary connected graph
v0   - is the initial beginning vertex
V    - is the set of all vertices in the graph G
S    - set of all vertices with permanent labels
n     - number of vertices in G
D    - set of distances to v0
C    - set of edges in G

Dijkstra Algorithm (graph G, vertex v0)
{
   S={v0}
   For i = 1 to n
        D[i] = C[v0,i]

   For i = 1 to n-1
        Choose a vertex w in V-S such that D[w] is minimum
        Add w to S
        For each vertex v in V-S
                D[v] = min(D[v], D[w] + C[w,v])
}

Click here to see an interactive example of Dijkstra's Algorithm.
Or move on to the next page to go directly to the next section.

Back to Dijkstra's Algorithm
Back to Dijkstra's Algorithm
On to
Flow Problems
On to Flow Problems